package leecode

import "fmt"

func canPartition(nums []int) bool {
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
	}
	if sum%2 == 1 {
		return false
	}
	target := sum / 2

	dp := make([]int, target+1) //容量为j的背包, 所背的物品最大价值
	// 01 背包
	for i := 0; i < len(nums); i++ {
		for j := target; j >= nums[i]; j-- {
			// dp[j] = max(dp[j], dp[j-nums[i]]) + nums[i]
			dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]) //物品i是否要装
			fmt.Println(dp)
		}
	}
	if dp[target] == target { //容量为target的背包,数组内的元素内将其装满
		return true
	}
	return false
}
